# 作者：一只牛吗
# 2025 年03月 03日 03时 15分 29秒
# 1278599690@qq.com
# 结点的定义是通过类来实现的，结点包含两个属性：val和left、right，分别表示结点的值和左右子结点。
class TreeNode:
    def __init__(self, val=-1, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


# 二叉树的定义是通过类来实现的，二叉树包含两个属性：root和size，分别表示根结点和结点个数。
class BinaryTree:
    def __init__(self):
        self.root: TreeNode = None
        self.auxiliary_queue = []

    def level_order_build(self, node):
        if self.root is None:
            self.root = node
            self.auxiliary_queue.append(node)
        else:
            self.auxiliary_queue.append(node)
            if self.auxiliary_queue[0].left is None:
                self.auxiliary_queue[0].left = node
            else:
                self.auxiliary_queue[0].right = node
                self.auxiliary_queue.pop(0)

    def pre_traverse(self, node):
        if node is None:
            return
        print(node.val, end=' ')
        self.pre_traverse(node.left)
        self.pre_traverse(node.right)

    def in_traverse(self, node):
        if node is None:
            return
        self.in_traverse(node.left)
        print(node.val, end=' ')
        self.in_traverse(node.right)

    def post_traverse(self, node):
        if node is None:
            return
        self.post_traverse(node.left)
        self.post_traverse(node.right)
        print(node.val, end=' ')

    def level_traverse(self, node):
        auxiliary_queue = []
        if node is None:
            return
        else:
            auxiliary_queue.append(node)
            while auxiliary_queue:
                print(auxiliary_queue[0].val, end=' ')
                if auxiliary_queue[0].left is not None:
                    auxiliary_queue.append(auxiliary_queue[0].left)
                if auxiliary_queue[0].right is not None:
                    auxiliary_queue.append(auxiliary_queue[0].right)
                auxiliary_queue.pop(0)


if __name__ == '__main__':
    # 构建二叉树
    binary_tree = BinaryTree()
    for i in range(1, 11):
        binary_tree.level_order_build(TreeNode(i))
    binary_tree.pre_traverse(binary_tree.root)
    print()
    binary_tree.in_traverse(binary_tree.root)
    print()
    binary_tree.post_traverse(binary_tree.root)
    print()
    binary_tree.level_traverse(binary_tree.root)
